﻿/****************************************************************
* http://dev-faqs.blogspot.com/2010/05/boyer-moore-algorithm.html
* 에서 가져온 Boyer - Moore string match algorithm 소스를
* 살짝 수정하였다. (unsigned char 문제)
*
* !!!!!!!!!!!!!!!!!!!!!!!!!!! 주의할 점 !!!!!!!!!!!!!!!!!!!!!!!!!!
* pIdx 가 int 범위의 1/2 를 넘지 않도록 할 것!
*****************************************************************/

#include <algorithm>
#include <vector>
#include <iostream>
#include <vector>
#include "search.h"

using namespace std;

vector<int> bmp_search(const string &text, const string &pattern)
{
	vector<int> location; // 찾은 문자열들의 위치

	size_t textSize = text.size();
	size_t patternSize = pattern.size();

	if(textSize == 0 || patternSize == 0)
	{
		return location;;
	}
	if(patternSize > textSize)
	{
		return location;
	}

	vector<int> bmpLast = compute_bmp_last(pattern);
	size_t tIdx = patternSize - 1;
	size_t pIdx = patternSize - 1;

	while(tIdx < textSize)
	{
		if(pattern[pIdx] == text[tIdx])
		{
			if(pIdx == 0)
			{   
				// match 찾았음
				location.push_back(tIdx);
				pIdx = patternSize - 1;
				tIdx = tIdx + patternSize;
				continue;
			}
			tIdx--;
			pIdx--;
		}
		else 
		{
			int lastOccur = bmpLast[static_cast<unsigned char>(text[tIdx])];
			if(lastOccur != -1)
			{
				if(static_cast<int>(pIdx) > lastOccur)
				{   // Case 1: last occurrence of char is to left or equal to the mismatch point 
					tIdx = tIdx + patternSize - (1 + lastOccur);
					pIdx = patternSize - 1;
				}
				else
				{   // Case 2: last occurrence of char is to right of the mismatch point
					tIdx = tIdx + patternSize - (pIdx);
					pIdx = patternSize - 1;
				}
			}
			else
			{   // Case 3: character is not found in the pattern string
				tIdx = tIdx + patternSize;
				pIdx = patternSize - 1;
			}
		}
	}
	return location;
}
vector<int> compute_bmp_last(const string &pattern)
{
	const size_t NUM_ASCII_CHARS = 256;
	vector<int> bmpLast(NUM_ASCII_CHARS);
	for(size_t i = 0; i < NUM_ASCII_CHARS; i++)
	{
		bmpLast[i] = -1;
	}
	for(size_t i = 0; i < pattern.size(); i++)
	{
		bmpLast[static_cast<unsigned char>(pattern[i])] = i;
	}
	return bmpLast;
}
